package com.leetcode.array_matrix;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/7/31 23:06
 */
public class FindDisappearedNumbers_448 {

    public List<Integer> findDisappearedNumbers(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int n = nums.length;
        for (int num : nums) {
            set.add(num);
        }
        for (int i = 1; i <= n; i++) {
            if (set.contains(i))
                set.remove(i);
            else
                set.add(i);
        }
        return new ArrayList<>(set);
    }

    public List<Integer> findDisappearedNumbers2(int[] nums) {

        // Iterate over each of the elements in the original array
        // 遍历每个元素，由于是在[1,N]内，所以可以将元素的值作为对应的坐标，然后将对应位置的元素乘以-1
        for (int i = 0; i < nums.length; i++) {

            // Treat the value as the new index
            int newIndex = Math.abs(nums[i]) - 1;

            // Check the magnitude of value at this new index
            // If the magnitude is positive, make it negative
            // thus indicating that the number nums[i] has
            // appeared or has been visited.
            // 只访问为正数的值！剩下的为正数即为未访问的index
            if (nums[newIndex] > 0) {
                nums[newIndex] *= -1;
            }
        }

        // Response array that would contain the missing numbers
        List<Integer> result = new LinkedList<>();

        // Iterate over the numbers from 1 to N and add all those
        // that have positive magnitude in the array
        for (int i = 1; i <= nums.length; i++) {
            // 找到
            if (nums[i - 1] > 0) {
                result.add(i);
            }
        }

        return result;
    }

}
